package project.newCode.bbhierarchy;

import java.io.PrintWriter;
import java.util.ArrayList;

import project.newCode.surfaces.Box;
import project.newCode.surfaces.Hittable;

public class BBBalancedNode extends BBNode implements Hittable{

	public BBBalancedNode() {
	}

	public BBBalancedNode(ArrayList<Hittable> A, int AXIS)
	{
		int N=A.size();
		if(N==1) {
			left = A.get(0);
			right = null;
			bbox = A.get(0).boundingbox();
		}
		else if(N==2) {
			left = A.get(0);
			right = A.get(1);
			bbox = Box.combine(left.boundingbox(),right.boundingbox());
		}
		else {
//			System.out.println("Issuing findhalf");
			float midpoint = this.findHalf(A,AXIS,(int) Math.floor(N/2));
//			if(AXIS==0) {
//				for(int i=0; i<A.size();i++) {
//					System.out.println(A.get(i).boundingbox().getPmin().x + " "+midpoint+" x");
//				}
//			}
//			if(AXIS==1) {
//				for(int i=0; i<A.size();i++) {
//					System.out.println(A.get(i).boundingbox().getPmin().y + " "+midpoint+" y");
//				}
//			}
//			if(AXIS==2) {
//				for(int i=0; i<A.size();i++) {
//					System.out.println(A.get(i).boundingbox().getPmin().z + " "+midpoint+" z");
//				}
//			}
			ArrayList<Hittable> aleft = new ArrayList<Hittable>();
			ArrayList<Hittable> aright = new ArrayList<Hittable>();
			aleft.ensureCapacity((int) Math.ceil(N/2));
			aright.ensureCapacity((int) Math.ceil(N/2));
			this.partition(A,aleft,aright,midpoint,AXIS);
//			System.out.println("Partitioned  into "+aleft.size() +" and " + aright.size());
			left = new BBBalancedNode(aleft,(AXIS+1)%3);
			right = new BBBalancedNode(aright,(AXIS+1)%3);
			this.combinebox(left.boundingbox(), right.boundingbox());
		}
	}
	private void partition(ArrayList<Hittable> a, ArrayList<Hittable> left2,
				ArrayList<Hittable> right2, float midpoint, int AXIS) {
		int N = a.size();
		if(AXIS==0) {
			for (int i = 0; i<N; i++) {
				if(a.get(i).boundingbox().getPmin().x < midpoint) {
					left2.add(a.get(i));
				}
				else {
					right2.add(a.get(i));
				}
			}
		}
		if(AXIS==1) {
			for (int i = 0; i<N; i++) {
				if(a.get(i).boundingbox().getPmin().y < midpoint) {
					left2.add(a.get(i));
				}
				else {
					right2.add(a.get(i));
				}
			}
		}
		if(AXIS==2) {
			for (int i = 0; i<N; i++) {
				if(a.get(i).boundingbox().getPmin().z < midpoint) {
					left2.add(a.get(i));
				}
				else {
					right2.add(a.get(i));
				}
			}
		}
		if(left2.size() == 0) {
			for(int i=0; i<(int) Math.floor(N/2); i++) {
				left2.add(right2.remove(right2.size()-1));
			}
		}
	}

	protected float findHalf(ArrayList<Hittable> A, int AXIS, int k) {
		int N = A.size();
//		if(N==0) {
//			System.out.println("Error! Array of length zero!");
//			Box b = null;
//			b.boundingbox();
//		}
		int pivot = (int) Math.floor(Math.random()*(N-1));
		ArrayList<Hittable> left = new ArrayList<Hittable>();
		ArrayList<Hittable> right = new ArrayList<Hittable>();
		this.split(A, left, right, pivot, AXIS);
//		System.out.println("Splitting "+A.size()+" with k "+k+ " left "+left.size()+ " right "+right.size());
		if(k==left.size()+1) {
//			System.out.println("returning something");
			if(AXIS==0) {
				return A.get(k-1).boundingbox().getPmin().x;
			}
			if(AXIS==1) {
				return A.get(k-1).boundingbox().getPmin().y;
			}
			if(AXIS==2) {
				return A.get(k-1).boundingbox().getPmin().z;
			}
		}
		if(k<=left.size()) {
			return this.findHalf(left, AXIS, k);
		}
		if(k>left.size()+1) {
			return this.findHalf(right, AXIS, k-(left.size()+1));
		}
		return 0;
	}
	protected void split(ArrayList<Hittable> A, ArrayList<Hittable> left, ArrayList<Hittable> right,int pivot, int AXIS) {
		int N = A.size();
		boolean deleted = false;
		if(AXIS==0) {
			for(int i=0; i<N; i++) {
				if(!deleted && A.get(i).boundingbox().getPmin().x == A.get(pivot).boundingbox().getPmin().x) {
					deleted = true;
				}
				else if(A.get(i).boundingbox().getPmin().x <= A.get(pivot).boundingbox().getPmin().x) {
					left.add(A.get(i));
				}
				else {
					right.add(A.get(i));
				}
			}
		}
		if(AXIS==1) {
			for(int i=0; i<N; i++) {
				if(!deleted && A.get(i).boundingbox().getPmin().y == A.get(pivot).boundingbox().getPmin().y) {
					deleted = true;
				}
				else if(A.get(i).boundingbox().getPmin().y <= A.get(pivot).boundingbox().getPmin().y) {
					left.add(A.get(i));
				}
				else {
					right.add(A.get(i));
				}
			}
		}
		if(AXIS==2) {
			for(int i=0; i<N; i++) {
				if(!deleted && A.get(i).boundingbox().getPmin().z == A.get(pivot).boundingbox().getPmin().z) {
					deleted = true;
				}
				else if(A.get(i).boundingbox().getPmin().z <= A.get(pivot).boundingbox().getPmin().z) {
					left.add(A.get(i));
				}
				else {
					right.add(A.get(i));
				}
			}
		}
	}

	// dirty method
	public void print(PrintWriter pr) {
		pr.println(bbox.toString());
		if(left instanceof BBBalancedNode) {
			((BBBalancedNode) left).print(pr);
		}
		if(right instanceof BBBalancedNode) {
			((BBBalancedNode) right).print(pr);
		}
	}

}
